﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>
#include <cstring>
using namespace std;


//class Solution {
//    const int x = pow(10, 9) + 7;
//public:
//    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
//        int m = group.size();
//        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
//
//        for (int j = 0; j <= n; j++) dp[j][0] = 1;
//
//        for (int i = 1; i <= m; i++)
//        {
//            for (int j = n; j >= 0; j--)
//            {
//                for (int k = minProfit; k >= 0; k--)
//                {
//                    if (j >= group[i - 1])
//                        dp[j][k] = (dp[j][k] + dp[j - group[i - 1]][max(k - profit[i - 1], 0)]) % x;
//                }
//            }
//        }
//        return dp[n][minProfit];
//    }
//};


//class Solution {
//public:
//    int combinationSum4(vector<int>& nums, int target) {
//        int n = nums.size();
//        vector<int> dp(target + 1);
//        dp[0] = 1;
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 0; j <= target; j++)
//            {
//                if (j >= nums[i - 1])
//                    dp[j] += dp[j - nums[i - 1]];
//            }
//        }
//        return dp[target];
//    }
//};


// 下面的数组问题，首选开辟数组法解决
//class Solution {
//public:
//    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
//        vector<int> nums;
//        int i = 0, j = 0;
//        while (i < m && j < n)
//        {
//            if (nums1[i] < nums2[j])
//            {
//                nums.push_back(nums1[i]);
//                i++;
//            }
//            else
//            {
//                nums.push_back(nums2[j]);
//                j++;
//            }
//        }
//        while (i < m)
//        {
//            nums.push_back(nums1[i]);
//            i++;
//        }
//        while (j < n)
//        {
//            nums.push_back(nums2[j]);
//            j++;
//        }
//
//        //// 开辟数组，使用sort
//        //vector<int> nums;
//        //for (int i = 0; i < m; i++)
//        //{
//        //    nums.push_back(nums1[i]);
//        //}
//        //for (int i = 0; i < n; i++)
//        //{
//        //    nums.push_back(nums2[i]);
//        //}
//        //sort(nums.begin(), nums.end());
//        //nums1.swap(nums);
//
//        nums1.swap(nums);
//    }
//};

//class Solution {
//public:
//    int removeElement(vector<int>& nums, int val) {
//	      // 开辟数组法
//        vector<int> v;
//        int n = 0;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            if (nums[i] != val) v.push_back(nums[i]);
//        }
//        n = v.size();
//        nums.swap(v);
//        return n;
//    }
//};

//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums) {
//        vector<int> v;
//        int n = 0;
//        v.push_back(nums[0]);
//        for (int i = 1; i < nums.size(); i++)
//        {
//            if (nums[i] != v.back())
//                v.push_back(nums[i]);
//        }
//        n = v.size();
//        nums.swap(v);
//        return n;
//    }
//};

//双指针法，该方法用两个整数划分
//一个表示后面的位置已经处理过的，一个数组后面的元素进行处理
//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums) {
//        int n = nums.size();
//        if (n <= 2) return n;
//        int left = 2, right = 2;
//        // left位置表示前面的元素都已经被处理
//        // right遍历完时，表示元素全部已被处理
//        while (right < n)
//        {
//            while (right < n && nums[right] == nums[left - 2])
//            {
//                right++;
//            }
//            if (right == n) break;
//            nums[left] = nums[right];
//            left++;
//            right++;
//        }
//        return left;
//    }
//};

//class Solution {
//public:
//    int majorityElement(vector<int>& nums) {
//        int n = nums.size(), m = n / 2;
//        if (n == 1) return nums.front();
//        int count = 1;
//        sort(nums.begin(), nums.end());
//        for (int i = 1; i < n; i++)
//        {
//            if (nums[i] == nums[i - 1]) count++;
//            else count = 1;
//            if (count > m) return nums[i];
//        }
//        return 0;
//    }
//};


//class Solution {
//public:
//    void rotate(vector<int>& nums, int k) {
//        int n = nums.size();
//        vector<int> v(n);
//        k %= n;
//        if (k != 0)
//        {
//            for (int i = 0, j = n - k; i < n; i++)
//            {
//                v[i] = nums[j];
//                j = (j + 1) % n;
//            }
//            nums.swap(v);
//        }
//    }
//};

//class Solution {
//public:
//    int maxProfit(vector<int>& prices) {
//        int n = prices.size();
//        if (n == 1) return 0;
//        vector<int> dp(n);
//        int minbuy = INT_MAX, maxprofit = 0;
//        for (int i = 0; i < n; i++)
//        {
//            minbuy = min(minbuy, prices[i]);
//            if (prices[i] - minbuy > 0)
//            {
//                dp[i] = prices[i] - minbuy;
//                maxprofit = max(maxprofit, dp[i]);
//            }
//        }
//        return maxprofit;
//    }
//};

//class Solution {
//public:
//    int maxProfit(vector<int>& prices) {
//        int n = prices.size();
//        vector<int> p(n + 1, INT_MIN);
//        vector<int> g(n + 1);
//
//        for (int i = 1; i <= n; i++)
//        {
//            p[i] = max(p[i - 1], g[i - 1] - prices[i - 1]);
//            g[i] = max(g[i - 1], p[i - 1] + prices[i - 1]);
//        }
//        return g[n];
//    }
//};

//class Solution {
//public:
//    bool canJump(vector<int>& nums) {
//        int n = nums.size();
//        int m = 0;
//        for (int i = 0; i < n; i++)
//        {
//            if (m >= i)
//            {
//                m = max(m, i + nums[i]);
//                if (i + nums[i] >= n - 1)
//                    return true;
//            }
//        }
//        return false;
//    }
//};

